﻿//__________________________________________________________________________________
// Вечный Странник, Маленькая Комната                                               |
//__________________________________________________________________________________|
//  Этот файл содержит                                                              |
//  класс Graph - граф                                                              |
//__________________________________________________________________________________|

using System;
using System.Collections.Specialized;
using System.Collections.Generic;
using System.Text;

namespace GraphLib
{
    public class Graph<V,E> where V : IVertex where E : IEdge
    {
        // список вершин графа
        private List<V> m_VertexList = new List<V>();
        // список рёбер графа
        private List<E> m_EdgeList = new List<E>();

        public Graph()
        {
        }

        // Добавление новой вершины в граф (в список вершин графа)
        public void AddVertex(V v)
        {
            //v.SetGraph(graph);
            m_VertexList.Add(v);
            //m_VertexList.Add(v.GetName(), v);
        }

        // Добавление в граф нового ребра (в список рёбер графа)
        public void AddEdge(E e)
        {
            m_EdgeList.Add(e);
            //m_EdgeList.Add(e.GetName(), e);
        }

        // Удаление из графа вершины по её имени.
        // При удалении вершины удаляются все принадлежащие ей рёбра.
        public void RemoveVertex(string name)
        {
            // список имён рёбер, подлежащих удалению
            List<string> temp = new List<string>();

            // определение рёбер, подлежащих удалению
            foreach (E e in m_EdgeList)
                if ((e.GetStart().GetName() == name) ||
                    (e.GetFinish().GetName() == name))
                    temp.Add(e.GetName());

            // удаление принадлежащих вершине рёбер
            for (int i = 0; i < temp.Count; i++)
                RemoveEdge(temp[i]);

            // удаление самой вершины
            m_VertexList.Remove(GetVertex(name));
        }

        // Удаление из графа ребра по его имени
        public void RemoveEdge(string name)
        {
            m_EdgeList.Remove(GetEdge(name));
        }

        // Получение вершины по её имени
        public V GetVertex(string name)
        {
            foreach (V v in m_VertexList)
                if (v.GetName() == name) return v;
            return default(V);
        }

        // Получение вершины по её индексу
        public V GetVertex(int index)
        {
            if (index < m_VertexList.Count)
                return m_VertexList[index];
            else
                return default(V);
        }

        // Получение ребра по его имени
        public E GetEdge(string name)
        {
            foreach (E e in m_EdgeList)
                if (e.GetName() == name) return e;
            return default(E);
        }

        // Получение ребра между двумя вершинами
        public E GetEdge(string SrcVertexName, string DestVertexName)
        {
            V srcV = GetVertex(SrcVertexName);
            List<E> lstEdges = GetOutEdges(SrcVertexName);
            foreach (E e in lstEdges)
                if (e.GetFinish().GetName() == DestVertexName) return e;
            return default(E);

        }

        // Получение числа вершин в графе
        public int GetCountVertexes()
        {
            return m_VertexList.Count;
        }

        // Получение числа рёбер в графе
        public int GetCountEdges()
        {
            return m_EdgeList.Count;
        }

        public List<V> GetInVertexes(string name)
        {
            List<V> lst = new List<V>();
            IVertex v = GetVertex(name);
            foreach (E e in m_EdgeList)
                if (e.GetFinish() == v) lst.Add((V)e.GetStart());
            return lst;
        }

        public List<V> GetOutVertexes(string name)
        {
            List<V> lst = new List<V>();
            IVertex v = GetVertex(name);
            foreach (E e in m_EdgeList)
                if (e.GetStart() == v) lst.Add((V)e.GetFinish());
            return lst;
        }

        // Получение списка рёбер входящих в вершину v
        public List<E> GetInEdges(string name)
        {
            List<E> lst = new List<E>();
            IVertex v = GetVertex(name);
            foreach (E e in m_EdgeList)
                if (e.GetFinish() == v) lst.Add(e);
            return lst;
        }

        // Получение списка рёбер выходящих из вершины v
        public List<E> GetOutEdges(string name)
        {
            List<E> lst = new List<E>();
            IVertex v = GetVertex(name);
            foreach (E e in m_EdgeList)
                if (e.GetStart() == v) lst.Add(e);
            return lst;
        }

        // Обход графа в глубину 
        // Параметры:
        //      srcName - имя начальной вершины
        //      destName - имя конечной вершины
        // Результат:
        //      список, содержащий вершины в порядке их прохождения
        //      от начальной до конечной
        // Алгоритм:
        //      помещаем начальную вершину в стек и объявляем её текущей.
        //      Пока стек не пуст и текущая вершина не является конечной:
        //      1. выбираем из стека очередную вершину, делая её текущей
        //      2. если из текущей вершины есть дуга, ведущая в ранее 
        //         не посещённую вершину(Р), то помещаем текущую вершину 
        //         в стек, объявляем вершину Р текущей и помещаем её в стек.
        //      Если текущая вершина не совпадает с конечной, то путь не существует.
        public List<V> DepthSearch(string srcName, string destName)
        {
            IVertex curVertex = GetVertex(srcName); 
            IVertex finVertex = GetVertex(destName);

            List<V> res = new List<V>();
            List<IVertex> visitedVertexes = new List<IVertex>();
            Stack<IVertex> stack = new Stack<IVertex>();

            stack.Push(curVertex);
            visitedVertexes.Add((V)curVertex);

            while ((stack.Count > 0) && (curVertex != finVertex))
            {
                curVertex = stack.Pop();
                List<E> out_edges = GetOutEdges(curVertex.GetName());
                foreach(E e in out_edges)
                    if (! visitedVertexes.Contains(e.GetFinish()))
                    {
                        stack.Push(curVertex);
                        curVertex = e.GetFinish();
                        stack.Push(curVertex);
                        visitedVertexes.Add(curVertex);
                        break;
                    }
            }

            if (curVertex == finVertex)
            {
                //res.AddRange(stack);
                //res.Reverse();
                while (stack.Count > 0)
                    res.Add((V)stack.Pop());
                return res;
            }
            else return null;
        }

        // Выполнение топологической сортировки
        // Тополог. сортировка возможна только если граф не имеет циклов
        // и сводится к отысканию разбиения множества вершин графа на
        // упорядоченные подмножества (уровни)
        // Результат:
        //      отсортированный список вершин 
        public List<V> TopologSort()
        {
            // Алгоритм Демукрона
            int VertexCount = m_VertexList.Count;
            // рабочая строка
            int[] calcStr = new int[VertexCount];
            // кол-во входящих вершин
            int[] inVertexCount = new int[VertexCount];
            int num = 0;
            int sum = 0;

            List<V> res = new List<V>();
            List<int> t_i = new List<int>();
            List<int> visited_i = new List<int>();
            List<int> t_ii = new List<int>();

            for (int i = 0; i < VertexCount; i++)
            {
                //m_VertexList[i].SortNum = -1;                
                inVertexCount[i] = GetInVertexes(m_VertexList[i].GetName()).Count;
                calcStr[i] = inVertexCount[i];
                sum += calcStr[i];
            }

            while (sum > 0)
            {
                    for (int i = 0; i < VertexCount; i++)
                {
                        int v_count = 0;
                        int e_count = 0;
                        while (v_count == 0)
                        {
                    if (calcStr[i] == e_count)
                        {
                            if (!res.Contains(m_VertexList[i])) res.Add(m_VertexList[i]);
                            if (!t_i.Contains(i) && (!visited_i.Contains(i)))
                            {
                                t_i.Add(i);
                                visited_i.Add(i);
                            }
                        v_count++;
                        }
                            if (v_count==0) {e_count++;}
                        }
                    for (int j = 0; j < t_i.Count; j++)
                        if ( !t_ii.Contains(t_i[j]))
                            for (int k = 0; k < VertexCount; k++)
                                if (GetOutVertexes(m_VertexList[t_i[j]].GetName()).Contains(m_VertexList[k]))
                                {
                                    calcStr[k] = calcStr[k] - 1;
                                    sum -= 1;
                                    t_ii.Add(i);
                                }
                    }
                
                num += 1;
                t_i.Clear();

            }

            for (int i = 0; i < VertexCount; i++)
                if (calcStr[i] == 0)
                    if (!res.Contains(m_VertexList[i])) res.Add(m_VertexList[i]);
                    //if (m_VertexList[i].SortNum == -1)
                        //m_VertexList[i].SortNum = num;
            return res;

        }

        // Алгоритм Дейкстра для поиска кратчайшего пути в графе
        // Граф не должен содержать рёбер с отрицательным весом.
        // Параметры:
        //      SrcVertexName - имя стартовой дуги; 
        //      DestVertexName - имя финишной дуги
        // Результат:
        //      список, содержащий вершины в порядке их прохождения
        //      от начальной до конечной
        // Если граф содержит рёбра с отрицательным весом, то возвращается пустой путь.
        public List<V> DeyxtraAlg(string SrcVertexName, string DestVertexName)
        {
            // список, хранящий найденный кратчайший путь
            List<V> res = new List<V>();
            for (int i = 0; i < m_EdgeList.Count; i++)
                if (m_EdgeList[i].Weight < 0) return res;

            // стартовая вершина
            V src = GetVertex(SrcVertexName);
            // финишная вершина
            V dest = GetVertex(DestVertexName);
            // список имён обрабатываемых вершин
            List<string> T = new List<string>();
            // количество вершин в графе
            int count = m_VertexList.Count;
            // длинны путей от стартовой до каждой из вершин
            Dictionary<string, double> d = new Dictionary<string, double>();
            string tFinVertex = SrcVertexName;
            res.Add(src);
            if (count != 0)
            {
                // начальное заполнение длин путей
                for (int i = 0; i < count; i++)
                {
                    string cur_name = m_VertexList[i].GetName();
                    E e = GetEdge(SrcVertexName, m_VertexList[i].GetName());

                    if (e != null) d[cur_name] = e.Weight;
                    else d[cur_name] = double.PositiveInfinity;

                    T.Add(m_VertexList[i].GetName());
                }
                d[SrcVertexName] = 0;

                // изначально Т содержит все вершины, кроме стартовой
                T.Remove(src.GetName());

                // пока есть, что обрабатывать
                while ((T.Count != 0)&&(tFinVertex != DestVertexName))
                {
                    string MinWayVertexName = T[0];
                    double MinWay = d[MinWayVertexName];
                    // выбираем вершину, до которой текущий путь минимален
                    for (int i = 0; i < T.Count; i++)
                    {
                        string cur_name = T[i];
                        if (d[cur_name] < MinWay)
                        {
                            MinWay = d[cur_name];
                            MinWayVertexName = cur_name;
                        }
                    }
                    // удаляем вершину с мин. путём из списка обработки
                    T.Remove(MinWayVertexName);
                    res.Add(GetVertex(MinWayVertexName));
                    tFinVertex = MinWayVertexName;

                    for (int i = 0; i < T.Count; i++)
                    {
                        E e = GetEdge(MinWayVertexName, T[i]);
                        if (e != null) 
                            d[T[i]] = Math.Min(d[T[i]], d[MinWayVertexName]+e.Weight);
                    }

                }
            }
            return res;
        }

        public List<V> EulerCycl(string StartVertexName)
        {
            List<E> BadEdges = new List<E>();

            // список, хранящий найденный цикл
            List<V> res = new List<V>();
            V startVertex = GetVertex(StartVertexName);

            Stack<IVertex> stack = new Stack<IVertex>();
            stack.Push(startVertex);
            while (stack.Count != 0)
            {
                IVertex v = stack.Pop();
                List<E> outEdges = GetOutEdges(v.GetName());
                if ((outEdges.Count != 0) && (! BadEdges.Contains(outEdges[0])))
                {
                    stack.Push(v);
                    stack.Push(outEdges[0].GetFinish());
                    BadEdges.Add(outEdges[0]);
                }
                else res.Add((V)v);

            }
            if (m_EdgeList.Count != BadEdges.Count) res = null;
            if (res != null) res.Reverse();
            return res;
        }


    }
}
